﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
// 原题连接：https://leetcode.cn/problems/minimum-string-length-after-removing-substrings/
/*
题目描述：
给你一个仅由 大写 英文字符组成的字符串 s 。
你可以对此字符串执行一些操作，在每一步操作中，你可以从 s 中删除 任一个 "AB" 或 "CD" 子字符串。
通过执行操作，删除所有 "AB" 和 "CD" 子串，返回可获得的最终字符串的 最小 可能长度。
注意，删除子串后，重新连接出的字符串可能会产生新的 "AB" 或 "CD" 子串。

 

示例 1：
输入：s = "ABFCACDB"
输出：2
解释：你可以执行下述操作：
- 从 "ABFCACDB" 中删除子串 "AB"，得到 s = "FCACDB" 。
- 从 "FCACDB" 中删除子串 "CD"，得到 s = "FCAB" 。
- 从 "FCAB" 中删除子串 "AB"，得到 s = "FC" 。
最终字符串的长度为 2 。
可以证明 2 是可获得的最小长度。

示例 2：
输入：s = "ACBBD"
输出：5
解释：无法执行操作，字符串长度不变。
 

提示：
1 <= s.length <= 100
s 仅由大写英文字母组成
*/

// 开始解题：
// 先将栈实现一下
// 重定义数据类型
typedef char DataType;

// 定义栈结构
typedef struct stack {
	DataType* data;
	int top;
	int capacity;
} Stack;

// 栈的初始化
void StackInit(Stack* ps);

// 压栈
void StackPush(Stack* ps, DataType x);
// 弹栈
void StackPop(Stack* ps);
// 返回栈顶数据
DataType StackTop(Stack* ps);
// 返回栈的数据个数
int StackSize(Stack* ps);
// 判断栈是否为空
bool StackEmpty(Stack* ps);
// 栈的销毁
void DestroyStack(Stack* ps);

// 栈的初始化
void StackInit(Stack* ps) {
	assert(ps);
	ps->data = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

// 压栈
void StackPush(Stack* ps, DataType x) {
	assert(ps);
	// 检查是否需要增容
	if (ps->top == ps->capacity) {
		int newCapacity = ps->capacity == 0 ? 10 : ps->capacity * 2;
		DataType* temp = (DataType*)realloc(ps->data, newCapacity * sizeof(DataType));
		if (NULL == temp) {
			perror("ralloc fail!\n");
			exit(-1);
		}
		ps->data = temp;
		ps->capacity = newCapacity;
	}
	ps->data[ps->top] = x;
	ps->top++;
}

// 弹栈
void StackPop(Stack* ps) {
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}

// 返回栈顶数据
DataType StackTop(Stack* ps) {
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->data[ps->top - 1];
}

// 返回栈的数据个数
int StackSize(Stack* ps) {
	assert(ps);
	assert(ps->top >= 0);
	return ps->top;
}

// 判断栈是否为空
bool StackEmpty(Stack* ps) {
	assert(ps);
	return ps->top == 0;
}

// 栈的销毁
void DestroyStack(Stack* ps) {
	assert(ps);
	free(ps->data);
	ps->data = NULL;
	ps->top = 0;
	ps->capacity = 0;
}








int minLength(char* s) {
	assert(s);
	Stack strStack;
	StackInit(&strStack);
	int i = 0;
	int len = strlen(s);
	for (i = 0; i < len; i++) {
		if (StackEmpty(&strStack)) {
			StackPush(&strStack, s[i]);
		}
		else if ((s[i] == 'B' && StackTop(&strStack) == 'A') || (s[i] == 'D' && StackTop(&strStack) == 'C')) {
			StackPop(&strStack);
		}
		else {
			StackPush(&strStack, s[i]);
		}
	}
	int result = StackSize(&strStack);
	DestroyStack(&strStack);
	return result;
}